package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/design-twitter/'>设计推特(Design Twitter)</a>
 * <p>设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。</p>
 * <p>
 * 实现 Twitter 类：
 *     <ul>
 *         <li>Twitter() 初始化简易版推特对象</li>
 *         <li>void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。</li>
 *         <li>List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近  10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。</li>
 *         <li>void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。</li>
 *         <li>void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例：
 *      输入
 *          ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
 *          [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
 *      输出
 *          [null, null, [5], null, null, [6, 5], null, [5]]
 *
 *      解释
 *          Twitter twitter = new Twitter();
 *          twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
 *          twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
 *          twitter.follow(1, 2);    // 用户 1 关注了用户 2
 *          twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
 *          twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
 *          twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
 *          twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *  <li>1 <= userId, followerId, followeeId <= 500</li>
 *  <li>0 <= tweetId <= 10^4</li>
 *  <li>所有推特的 ID 都互不相同</li>
 *  <li>postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10^4 次</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/4 17:06
 */
public class LC0355Twitter_M {

    static class Twitter {
        /**
         * 用户id 和 推文(单链表结构)的对应关系
         */
        private final Map<Integer, Tweet> twitterMap;
        /**
         * 用户id 和关注列表的对应关系
         */
        private final Map<Integer, Set<Integer>> followingMap;
        /**
         * 时间戳，用于记录发布推文的时间，用户每发布一条推文之前+1
         */
        private static int timestamp = 0;

        public Twitter() {
            twitterMap = new HashMap<>();
            followingMap = new HashMap<>();
        }

        /**
         * 根据给定的 tweetId 和 userId 创建一条新推文。
         * <p>根据当前 tweetId 和 timestamp 创建Tweet对象。存到twitterMap中key为userId的value的头部</p>
         */
        public void postTweet(int userId, int tweetId) {
            timestamp++;
            Tweet sourceTweet = twitterMap.get(userId);
            Tweet newTweet = new Tweet(tweetId, timestamp);
            if (sourceTweet == null) {
                twitterMap.put(userId, newTweet);
            } else {
                newTweet.next = sourceTweet;
                twitterMap.put(userId, newTweet);
            }
        }

        /**
         * 将自己的推文链表，和关注列表的推文链表，找出10条最近创建的。
         * <p>使用按照推文时间戳排序的大根堆，将所有的推文链表放进去，每次取堆首的推文，添加到结果集中</p>
         */
        public List<Integer> getNewsFeed(int userId) {
            // 创建一个大根堆
            PriorityQueue<Tweet> maxHead = new PriorityQueue<>(((o1, o2) -> o2.timestamp - o1.timestamp));
            if (twitterMap.containsKey(userId)) {
                maxHead.offer(twitterMap.get(userId));
            }
            Set<Integer> followingSet = followingMap.get(userId);
            if (followingSet != null && !followingSet.isEmpty()) {
                for (Integer followingUserId : followingSet) {
                    Tweet tweet = twitterMap.get(followingUserId);
                    if (tweet != null) {
                        maxHead.offer(tweet);
                    }
                }
            }
            List<Integer> resList = new ArrayList<>(10);
            while (!maxHead.isEmpty() && resList.size() < 10) {
                Tweet head = maxHead.poll();
                resList.add(head.id);
                head = head.next;
                if (head != null) {
                    maxHead.offer(head);
                }
            }
            return resList;
        }

        /**
         * ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
         */
        public void follow(int followerId, int followeeId) {
            if (followerId == followeeId) {
                return;
            }
            Set<Integer> followingSet = followingMap.getOrDefault(followerId, new HashSet<>());
            followingSet.add(followeeId);
            followingMap.put(followerId, followingSet);
        }

        /**
         * ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户
         */
        public void unfollow(int followerId, int followeeId) {
            if (followerId == followeeId) {
                return;
            }
            Set<Integer> followingSet = followingMap.get(followerId);
            if (followingSet == null) {
                return;
            }
            followingSet.remove(followeeId);

        }

        private static class Tweet {
            /**
             * 推文id
             */
            private final int id;
            /**
             * 发送推文的时间戳
             */
            private final int timestamp;
            /**
             * 单链表结构，下一条推文
             */
            private Tweet next;

            public Tweet(int id, int timestamp) {
                this.id = id;
                this.timestamp = timestamp;
            }
        }
    }

    public static void main(String[] args) {
        Twitter twitter = new Twitter();
        twitter.postTweet(1, 5);
        System.out.print("用户 userId=1 的推文列表：");
        for (Integer integer : twitter.getNewsFeed(1)) {
            System.out.print(integer + ", ");
        }
        System.out.println();
        twitter.follow(1, 2);
        twitter.postTweet(2, 6);
        System.out.print("用户 userId=1 的推文列表：");
        for (Integer integer : twitter.getNewsFeed(1)) {
            System.out.print(integer + ", ");
        }
        System.out.println();
        twitter.unfollow(1, 2);
        System.out.print("用户 userId=1 的推文列表：");
        for (Integer integer : twitter.getNewsFeed(1)) {
            System.out.print(integer + ", ");
        }
        System.out.println();
    }
}
